//完全二叉树 是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。 
//
// 设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。 
//
// 实现 CBTInserter 类: 
//
// 
// CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构； 
// CBTInserter.insert(int v) 向树中插入一个值为 Node.val == val的新节点 TreeNode。使树保持完全二叉树的状态
//，并返回插入节点 TreeNode 的父节点的值； 
// CBTInserter.get_root() 将返回树的头节点。 
// 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//
// 
//输入
//["CBTInserter", "insert", "insert", "get_root"]
//[[[1, 2]], [3], [4], []]
//输出
//[null, 1, 2, [1, 2, 3, 4]]
//
//解释
//CBTInserter cBTInserter = new CBTInserter([1, 2]);
//cBTInserter.insert(3);  // 返回 1
//cBTInserter.insert(4);  // 返回 2
//cBTInserter.get_root(); // 返回 [1, 2, 3, 4] 
//
// 
//
// 提示： 
//
// 
// 树中节点数量范围为 [1, 1000] 
// 0 <= Node.val <= 5000 
// root 是完全二叉树 
// 0 <= val <= 5000 
// 每个测试用例最多调用 insert 和 get_root 操作 10⁴ 次 
// 
//
// Related Topics 树 广度优先搜索 设计 二叉树 👍 90 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class _919_CompleteBinaryTreeInserter {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2), null);
        CBTInserter solution = new _919_CompleteBinaryTreeInserter().new CBTInserter(root);
        System.out.println(solution.insert(3));
        System.out.println(solution.insert(4));
        TreeNode res = solution.get_root();
        System.out.println();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class CBTInserter {
        TreeNode root;
        Deque<TreeNode> queue;

        public CBTInserter(TreeNode root) {
            queue = new ArrayDeque<>();
            if (root != null) {
                this.root = root;
                queue.addLast(root);
                while (!queue.isEmpty()) {
                    if (queue.peekFirst().left != null && queue.peekFirst().right != null) {
                        TreeNode cur = queue.removeFirst();
                        if (cur.left != null) {
                            queue.addLast(cur.left);
                        }
                        if (cur.right != null) {
                            queue.addLast(cur.right);
                        }
                    } else if (queue.peekFirst().left != null) {
                        queue.addLast(queue.peekFirst().left);
                        break;
                    } else {
                        break;
                    }
                }
            }
        }

        public int insert(int val) {
            if (this.root == null) {
                this.root = new TreeNode(val);
                queue.addLast(root);
                return -1;
            } else {
                int res = queue.peekFirst().val;
                if (queue.peekFirst().left == null) {
                    TreeNode temp = new TreeNode(val);
                    queue.peekFirst().left = temp;
                    queue.addLast(temp);
                } else {
                    TreeNode temp = new TreeNode(val);
                    queue.removeFirst().right = temp;
                    queue.addLast(temp);
                }
                return res;
            }
        }

        public TreeNode get_root() {
            return root;
        }
    }

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(val);
 * TreeNode param_2 = obj.get_root();
 */
//leetcode submit region end(Prohibit modification and deletion)

}